package ac;

public class BM {
    private final String pattern;
    private int[] badTable;
    private int[] goodTable;

    public BM(final String pattern) {
        this.pattern = pattern;
        buildBadTable();
        buildGoodTable();
    }

    public boolean containsMatch(final String target) {
        if (pattern.length() > target.length()) {
            return false;
        }

        for (int i = pattern.length() - 1, j; i < target.length();) {
            for (j = pattern.length() - 1; target.charAt(i) == pattern.charAt(j); i--, j--) {
                if (j == 0) {
                    return true;
                }
            }
            i += Math.max(goodTable[pattern.length() - j - 1], badTable[target.charAt(i)]);
        }
        return false;
    }

    public void buildBadTable() {
        badTable = new int[0xff];

        for (int i = 0; i < badTable.length; i++) {
            badTable[i] = pattern.length();
        }
        for (int i = 0; i < pattern.length() - 1; i++) {
            int k = pattern.charAt(i);
            badTable[k] = pattern.length() - 1 - i;
        }
    }

    public void buildGoodTable() {
        goodTable = new int[pattern.length()];
        int lastPrefixPosition = pattern.length();

        for (int i = pattern.length() - 1; i >= 0; --i) {
            if (isPrefix(i + 1)) {
                lastPrefixPosition = i + 1;
            }
            goodTable[pattern.length() - 1 - i] = lastPrefixPosition - i + pattern.length() - 1;
        }

        for (int i = 0; i < pattern.length() - 1; ++i) {
            int slen = suffixLength(i);
            goodTable[slen] = pattern.length() - 1 - i + slen;
        }
    }

    private boolean isPrefix(int p) {
        for (int i = p, j = 0; i < pattern.length(); ++i, ++j) {
            if (pattern.charAt(i) != pattern.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    private int suffixLength(int p) {
        int length = 0;
        for (int i = p, j = pattern.length() - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) {
            length += 1;
        }
        return length;
    }
}